package leetcode.D200.T146;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: duyuzhou
 * @Create: 2022-04-20 0:21:14 星期三
 */
public class LRUCache2 {
    static class Node {
        int key;
        int value;
        Node prev;
        Node next;
        Node() {}
        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    static class DoubleList {
        Node head;
        Node tail;
        int size;

        void addNode(Node node) {
            if (size == 0) {
                head = node;
                tail = node;
            } else {
                tail.next = node;
                node.prev = tail;
                tail = node;
            }
            size++;
        }

        void refreshNode(Node node) {
            if (node == tail)
                return;
            else if (node == head) {
                head = node.next;
                head.prev = null;
                tail.next = node;
                node.prev = tail;
                node.next = null;
                tail = node;
            } else {
                node.prev.next = node.next;
                node.next.prev = node.prev;
                tail.next = node;
                node.prev = tail;
                node.next = null;
                tail = node;
            }
        }

        int removeOldest() {
            size--;
            int key = head.key;
            head = head.next;
            if (head != null)
                head.prev = null;
            return key;
        }

        int getSize() {
            return size;
        }
    }

    private DoubleList list = new DoubleList();
    private final Map<Integer, Node> map = new HashMap<>();
    private final int capacity;

    public LRUCache2(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        if (!map.containsKey(key))
            return -1;
        Node node = map.get(key);
        list.refreshNode(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            list.refreshNode(node);
        } else {
            Node node = new Node(key, value);
            if (list.getSize() == capacity) {
                int k = list.removeOldest();
                map.remove(k);
            }
            list.addNode(node);
            map.put(key, node);
        }
    }
}
